/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.gpstracking.Utils.Geometry;


import java.util.Collections;
import java.util.Comparator;

/**
 *
 * @author jmj
 */
public class Algorithms {
    public double ccw( Point a, Point b , Point c){
        return c.minus( a ).cross( b.minus(a)); 
    }
    public double area( Polygon p){
        double res = 0.0;
        int n = p.n;
        for( int i = 0; i <= n; i++){
            res += Math.abs( p.get( i ).cross( p.get(i % n) ) );
        }
        return res / 2.0;
    }
    public Polygon convexHull( Polygon p){
        
        Collections.sort(p.points, new Comparator<Point>(){
            
            public int compare(Point a, Point b) {
                if ( Double.compare( a.x , b.x) == 0 ){
                    return Double.compare(a.y, b.y);
                }
                return Double.compare(a.x, b.x);
            }
        });
        
        int n = p.n;
        Polygon hull = new Polygon(2*n) ;
        
        int k = 0;
        for( int i = 0; i < n; i++){
            if ( k >= 2 && Double.compare( ccw( hull.get(k-2), hull.get( k-1 ), p.get( i ) ) , 0 ) <= 0) k--;
            hull.set( k , p.get(i) );
        }
        int tmp = k + 1;
        for( int i = n - 1; i >= 0; i--){
            if ( k >= tmp && Double.compare( ccw( hull.get(k-2), hull.get( k-1 ), p.get( i ) ) , 0 ) <= 0  ) k--;
            hull.set( k , p.get(i) );
        }
        return hull;
    }
    public boolean inPoly( Point p, Polygon poly){
        poly.add( p );
        Polygon hull = convexHull( poly );
        for( int i = 0; i < hull.n ; i++){
            if ( hull.get(i).equals( p )){
                return false;
            }
        }
        return true;
    }
}
